home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / OTHELLO.ZIP / othello.c
Encoding:
C/C++ Source or Header  |  1995-04-15  |  44.3 KB  |  1,738 lines
  1. From: bet@std.sbi.com (Bennett Todd)
  2. Newsgroups: alt.sources
  3. Subject: Othello.c
  4. Date: 22 Jun 1994 03:23:45 GMT
  5. Organization: Salomon Brothers, Inc.
  6.  
  7. This is a fairly portable program I wrote to play othello for an AI class
  8. back in 1983. I wrote it using DeSmet C, and it has some special PC
  9. optimizations, under #ifdef DeSmet, that are non-portable. You'll need to
  10. blow out the #define DeSmet if you aren't using his C compiler. If your C
  11. compiler gets annoyed at illegal syntax within #if/#endif that isn't being
  12. compiled, then you'll also need to edit out the blocks that are ifdef
  13. DeSmet.
  14.  
  15. This program uses Alpha-Beta pruning of a minimax lookahead tree. It has a
  16. fairly tweaked board evaluation heuristic, with an edge strategy and so on.
  17. It is possibly over-optimized by modern standards, but this thing plays a
  18. strong game, on a 4.77MHz 8088 in 64K of RAM, with no move taking more than
  19. 30 seconds.
  20.  
  21. -Bennett
  22. bet@sbi.com
  23.  
  24.  
  25. /*
  26.  * Othello playing program. Fairly portable if DeSmet isn't defined;
  27.  * defining DeSmet enables some inline-assembler screen wizzery on PCs,
  28.  * using DeSmet C's convention for inline assembler.
  29.  *
  30.  * The code looks a _lot_ better if you display it with tabstops every
  31.  * four spaces, rather than every 8.
  32.  *
  33.  * Written in 1993 by Bennett Todd, with some help by John White, who
  34.  * designed the finite state automaton for edge strategy.
  35.  */
  36.  
  37. /*
  38.  
  39.     Plays othello using alpha-beta search.
  40.     Defining DEBUG_LEVEL as 1 sets enhanced error trapping, and
  41.                             2 gives run-time statistics
  42.                             3 enables enhanced run-time sanity checking
  43.     defining IBMPC generates non-portable PC optimization
  44.     defining DeSmet changes handling of '\n' on input
  45.  
  46.     Switches:
  47.     -f    gofirst (default=no)
  48.     -bn    allocate n boards: default=64, grows as branching factor*depth
  49.     -dn    look ahead n moves: default is variable, must be greater than 0
  50.     -rn reverse the initial board in various ways:
  51.  
  52.         -r1 reverse initial board setup; 'o' still goes first
  53.         -r2 reverse initial board setup; 'x' goes first
  54.         -r3  normal initial board setup; 'x' goes first
  55.  
  56. */
  57.  
  58. #include <stdio.h>
  59.  
  60. #define DEBUG_LEVEL 1
  61. #define DeSmet
  62.  
  63. /*
  64.     About the following defines:
  65.     BEST and WORST are upper and lower bounds, respectively, on the
  66.         worth of a board.
  67.     MAXSONS is the maximum number of possible moves from any given board,
  68.         used to size the sons array in a board node.
  69.     EMPTY, MINE, and HIS are values for the possible states of a square
  70.         on an othello board. In the original code, they were used as an
  71.         enumerated type, after the fashion of PASCAL. However, during
  72.         the process of optimizing the program, It was observed that
  73.         in the code
  74.             <expression>!=EMPTY
  75.         !=EMPTY doesn't change the logical value of the expression, and
  76.             <expression>==EMPTY is equivalent to !<expression>
  77.         Thus the contents of board cells are sometimes used as boolean
  78.         variables.
  79.         What's worse, many nested if expressions and switch statements
  80.         were removed by using values of board cells as subscripts into
  81.         arrays, a process which altogether exceeded any reasonable bounds
  82.         in the finite state machine found in the function worth.
  83. */
  84.  
  85. #define TRUE  1
  86. #define FALSE 0
  87. #define WORST -1000
  88. #define BEST   1000
  89. #define MAXSONS 30
  90. #define EMPTY '\0'
  91. #define MINE  '\1'
  92. #define HIS   '\2'
  93.  
  94. typedef struct boardtype
  95. {
  96.     struct boardtype *sons[MAXSONS];    /* pointers to descendants    */
  97.     int val;                            /* worth of board position    */
  98.     char *array[8];                        /* the board itself            */
  99. }
  100. BOARD;
  101.  
  102. BOARD *freeboards; /* pointer to head of linked list of free boards */
  103.  
  104. int maxdepth[60]=    /* maxdepth[movenumber] is the depth that alphabeta */
  105.     {                /* will search on the movenumber'th move            */
  106.         1, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  107.         3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  108.         3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  109.         3, 3, 3, 3, 3, 3, 4, 7, 6, 5, 4, 3, 2, 1, 1
  110.     },
  111.     maxboards=64,    /* default number of boards to allocate     */
  112.     reversed=FALSE, /* switch to reverse initial board position */
  113.     movenumber=0,    /* counter for what move we are on            */
  114.     time_out[3]=    /* timeout points, to hurry up if we are in    */
  115.     {                /* danger of overshooting 30 seconds        */
  116.         2000,2500,2800
  117.     },
  118.     start_dive=52,    /* the movenumber on which to switch worths */
  119.     gofirst=FALSE,    /* by default, the opponent goes first        */
  120.     max,            /* who is playing at any given instant        */
  121.     (*worth)(),        /* pointer to the current worth function    */
  122.     i_tran[64]=        /* i subscript generator                    */
  123.     {
  124.         0, 0, 0, 0, 0, 0, 0, 0,
  125.         1, 1, 1, 1, 1, 1, 1, 1,
  126.         2, 2, 2, 2, 2, 2, 2, 2,
  127.         3, 3, 3, 3, 3, 3, 3, 3,
  128.         4, 4, 4, 4, 4, 4, 4, 4,
  129.         5, 5, 5, 5, 5, 5, 5, 5,
  130.         6, 6, 6, 6, 6, 6, 6, 6,
  131.         7, 7, 7, 7, 7, 7, 7, 7
  132.     },
  133.     j_tran[64]=        /* j subscript generator                    */
  134.     {
  135.         0, 1, 2, 3, 4, 5, 6, 7,
  136.         0, 1, 2, 3, 4, 5, 6, 7,
  137.         0, 1, 2, 3, 4, 5, 6, 7,
  138.         0, 1, 2, 3, 4, 5, 6, 7,
  139.         0, 1, 2, 3, 4, 5, 6, 7,
  140.         0, 1, 2, 3, 4, 5, 6, 7,
  141.         0, 1, 2, 3, 4, 5, 6, 7,
  142.         0, 1, 2, 3, 4, 5, 6, 7
  143.     };
  144.  
  145. long time;            /* time tick holder, for stopwatch    */
  146.  
  147. /*
  148.     The array moves, declared below, is an array of pointers to arrays
  149.     of pointers to arrays of subscripts, ranging from 0 to 63.
  150.     A board is declared in the structure declaration above to be represented
  151.     by an array of 8 pointers to arrays of chars (8 per array). In my
  152.     initialization of the board structures, I explicitly allocate the row
  153.     arrays consecutively; therefore, board->array[0] can be taken as a
  154.     pointer to an array 64 long of chars, containing the cells of the board.
  155.     board->array[0][moves[i][j][k]] is the k-th step in th j-th direction
  156.     from the i-th cell in board. Moves is 64 long; moves[i] is variable
  157.     length (one for each direction in which a move is possible) delimited
  158.     with NULLs, and move[i][j] is variable length, delimited by i. In
  159.     other words, to walk as far as possible in the j-th direction from
  160.     cell i, you could use
  161.         for(k=0;i!=moves[i][j][k];k++)
  162.     though I didn't, since I use pointers to walk through the array.
  163.  
  164. */
  165.  
  166. char **moves[64],
  167.      print_chars[3]={' ','x','o'}; /* the character to print for a cell */
  168.  
  169. #if DEBUG_LEVEL > 1
  170. int allsons_called,
  171.     worth_called,
  172.     max_used_boards,
  173.     boards_in_use,        /* various variables to accumulate statistics */
  174.     greatest_branching,
  175.     alpha_prunes,
  176.     beta_prunes;
  177. #endif
  178. #if DEBUG_LEVEL > 2
  179.     int moves_checksum,
  180.         board_count=0;
  181.  
  182.     BOARD *board_bottom,
  183.           *board_end;
  184. #endif
  185.  
  186. #ifdef IBMPC
  187.     int line_number,        /* the current screen line number    */
  188.         screen_seg;            /* segment offset for video ram        */
  189.  
  190.     char scr_line[160];        /* output line--character data        */
  191.                             /* alternating with attribute bytes */
  192. #if DEBUG_LEVEL > 1
  193. #define BOARD_TOP 960
  194. #else
  195. #define BOARD_TOP 1120
  196. #endif
  197. #endif
  198.  
  199. main(argc,argv)
  200. int argc;
  201. char **argv;
  202. {
  203.     int i,
  204.         temp,
  205.         worth_1(),    /* necessary declarations to tell the compiler what     */
  206.         worth_2(),    /* kind of objects these are, for assignment to worth    */
  207.         oldmove;
  208.  
  209.     long time_tick();    /* only implemented on the IBM-PC, a stopwatch        */
  210.  
  211.     BOARD *root,            /* the root of the current tree, changed by     */
  212.           *firstboard();    /* both move() and getmove()                    */
  213.  
  214. #if DEBUG_LEVEL > 1
  215. #ifdef IBMPC
  216.     char *_showsp(),
  217.          *_memory();
  218. #endif
  219. #endif
  220.  
  221.     /* parse the switches on the command line    */
  222.     for(i=1;i<argc;i++)
  223.         /* all of which start with '-'    */
  224.         if(*argv[i]=='-')
  225.             switch(*++argv[i])
  226.             {
  227.                 case 'f':    /* set a boolean switch gofirst, and            */
  228.                 case 'F':    /* exchange how squares are printed                */
  229.                     gofirst=TRUE;
  230.                     temp=print_chars[1];
  231.                     print_chars[1]=print_chars[2];
  232.                     print_chars[2]=temp;
  233.                     break;
  234.                 case 'd':    /* force depth to be maxdepth for every move    */
  235.                 case 'D':
  236.                     if(isdigit(*++argv[i]))
  237.                     {
  238.                         maxdepth[0]=atoi(argv[i]);
  239.                         start_dive=60-maxdepth[0];
  240.                         for(temp=0;temp<59;temp++)
  241.                             maxdepth[temp+1]=maxdepth[temp];
  242.                     }
  243.                     else
  244.                         fprintf(stderr,"bad depth %s\n",argv[i]);
  245.                     break;
  246.                 case 'b':    /* change number of boards to allocate            */
  247.                 case 'B':
  248.                     if(isdigit(*++argv[i]))
  249.                         maxboards=atoi(argv[i]);
  250.                     else
  251.                         fprintf(stderr,"bad board limit %s\n",argv[i]);
  252.                     break;
  253.                 case 'r':    /* reverse board position in various ways        */
  254.                 case 'R':
  255.                     if(isdigit(*++argv[i]))
  256.                     {
  257.                         temp=atoi(argv[i]);
  258.                         if(temp%2)
  259.                             reversed=TRUE;
  260.                         if(temp>1)
  261.                         {
  262.                             temp=print_chars[1];
  263.                             print_chars[1]=print_chars[2];
  264.                             print_chars[2]=temp;
  265.                         }
  266.                     }
  267.                     else
  268.                         fprintf(stderr,"bad reverse switch %s\n",argv[i]);
  269.                     break;
  270.                 default:
  271.                     fprintf(stderr,"unknown switch %s ignored\n",argv[i]);
  272.                     break;
  273.             }
  274.         else
  275.             fprintf(stderr,"unknown arg %s ignored\n",argv[i]);
  276.  
  277. #ifdef IBMPC
  278.     init_screen();    /* initialize scr_line and screen_seg */
  279. #endif
  280.  
  281.     /* call various initialization routines            */
  282.     worth=worth_1;    /* the main heuristic function    */
  283.  
  284. #if DEBUG_LEVEL > 1
  285. #ifdef IBMPC
  286.     printf("freespace bottom %u\n",((unsigned int) _memory()));
  287.     printf("    stack    top %u\n",((unsigned int) _showsp()));
  288. #endif
  289. #endif
  290.  
  291.     initmoves();    /* initialize the array moves    */
  292.  
  293. #if DEBUG_LEVEL > 2
  294.     board_bottom=freeboards;
  295.     moves_checksum=check_moves();
  296. #endif
  297.  
  298.     initfree();            /* set up free boards list    */
  299.  
  300. #if DEBUG_LEVEL > 2
  301.     printf("allocated %d boards\n",board_count);
  302. #endif
  303.  
  304.     root=firstboard();    /* set up to play the game    */
  305.  
  306. #if DEBUG_LEVEL > 2
  307.     board_count--;
  308.     printf("which leaves %d to play with.\n",board_count);
  309. #endif
  310.  
  311.     time=time_tick();    /* and mark time            */
  312.  
  313.     if(gofirst)
  314.         move(&root);
  315.     else
  316.     {
  317.  
  318. #ifdef IBMPC
  319.     clear_home();    /* fast clear screen    */
  320. #else
  321.     putchar('\f');    /* slow one                */
  322. #endif
  323.  
  324.         putboard(root,NULL);    /* put only one board */
  325.     }
  326.  
  327.     oldmove=(-1); /* dummy out endgame flag, it's only starting now! */
  328.  
  329.     /* main game loop */
  330.     while(movenumber<60 && movenumber!=oldmove) /* game lasts 60 moves,        */
  331.     {                                            /* unless no one can move    */
  332.  
  333. #if DEBUG_LEVEL > 2
  334.         if(moves_checksum!=check_moves())
  335.         {
  336.             printf("Moves checksum failed. Sorry, boss.\n");
  337.             exit();
  338.         }
  339.         if(board_count!=count_boards())
  340.             printf("I seem to have mislain a board: %d/%d\n",
  341.                     board_count,count_boards());
  342. #endif
  343.  
  344.         if(movenumber>start_dive)    /* change to h*, the "true" h function    */
  345.         {
  346.             time_out[0]=time_out[1];
  347.             worth=worth_2;            /* only computable by looking to the end*/
  348.         }
  349.         oldmove=movenumber;            /* set to recognize if no one can move    */
  350.         getmove(&root);    /* get a move from the user    */
  351.         move(&root);    /* make a move                */
  352.     }
  353.     score(root);    /* report the result */
  354. }
  355.  
  356. /*
  357.     move makes a move on the (called-by-reference) board. It first
  358.     expands all possible moves with a call to allsons, with max set to
  359.     true (moves is trying to maximize the evaluation function), then uses
  360.     alphabeta to evaluate each possibility, picking the best.
  361.     Move is different from alphabeta mostly in that
  362.         a)    it always and only plays as max
  363.         b)    it must keep track of the actual boards, and not just
  364.             their values (alphabeta always reclaims as soon as possible)
  365.         c)    it is in charge of initializing everything for the search
  366.         d)    rather than returning a backed up value, it simply outputs the
  367.             move (and some other junk) and resets the root to point to the
  368.             new move.
  369. */
  370.  
  371. move(board)
  372. BOARD **board;
  373. {
  374.     BOARD *tempboard;
  375.  
  376.     int i,
  377.         n,
  378.         rush=0,            /* used to panic stop short of 30 seconds            */
  379.         temp,
  380.         alpha=WORST,    /* the root is max, and therefore has an alpha value*/
  381.         best=WORST-1,    /* must be worst than the worst possible value, so    */
  382.                         /* that a move will be picked even if they are all    */
  383.                         /* the worst.                                        */
  384.         bestboard;        /* subscript of the best board seen so far            */
  385.  
  386.     char *t1,            /* a couple of temporary pointers used to            */
  387.          *t2;            /* figure out exactly where I moved.                */
  388.  
  389.     long time_tick();    /* stopwatch function, implemented only on the PC    */
  390.  
  391.     max=TRUE;    /* let us get this straight, once and for all... */
  392.  
  393. #ifdef IBMPC
  394.     clear_home();    /* fast clear screen    */
  395. #else
  396.     putchar('\f');    /* slow one                */
  397. #endif
  398.  
  399.     /* read the following as "if( <number of sons found> == 0)"    */
  400.     if(!(n=allsons(*board)))    /* "==0" is equivalent to "!"    */
  401.     {
  402.         printf("I cannot move. Your turn.\n");
  403.         putboard(*board,NULL);    /* put the board so that he can see the */
  404.         return;                    /* result of his last move                */
  405.     }
  406.  
  407. #if DEBUG_LEVEL > 1
  408.     allsons_called=1;
  409.     worth_called=n;
  410.     boards_in_use=max_used_boards=1;    /* initialize variables to    */
  411.     greatest_branching=n;                /* accumulate statistics    */
  412.     alpha_prunes=0;
  413.     beta_prunes=0;
  414. #endif
  415.  
  416.     /* for every son */
  417.     for(i=0;i<n;i++)
  418.     {
  419.  
  420.         max=FALSE;    /* think as my opponent would think */
  421.  
  422.         /* if this is better than the best we have seen so far */
  423.         if(best<(temp=alphabeta((*board)->sons[i],maxdepth[movenumber],
  424.                                 alpha,BEST)))
  425.         {
  426.             best=alpha=temp;
  427.             bestboard=i;
  428.         }
  429.  
  430.         /* make sure we do not under any circumstances exceed 30 seconds */
  431.         if((time_tick()-time) > time_out[rush])
  432.         {
  433.             if(rush==2)
  434. #if DEBUG_LEVEL > 1
  435.             {
  436.                 line_number=0;
  437.                 fast_puts("buggering out, on account of lack of time!!");
  438. #endif
  439.                 goto outta_here;
  440.  
  441. #if DEBUG_LEVEL > 1
  442.             }
  443.             printf("I'm hurrying...\n");
  444. #endif
  445.  
  446.             rush++;
  447.             maxdepth[movenumber]--;
  448.         }
  449.     }
  450.  
  451. outta_here:
  452.     t1=(*board)->array[0]-1;                    /* set up pointers    */
  453.     t2=(*board)->sons[bestboard]->array[0]-1;    /* for comparison    */
  454. loop:
  455.     while(*++t1==(*++t2));    /* find different squares            */
  456.     if(*t1)    /* then this square was flipped, not actually moved */
  457.         goto loop;    /* so keep trying                            */
  458.  
  459.     /* temp gets the 0-63 subscript of the move */
  460.     temp=t1-(*board)->array[0];
  461.  
  462. #if DEBUG_LEVEL > 1
  463.     printf("I moved at %c %d in %5.2f seconds\n",
  464.             'a'+j_tran[temp],1+i_tran[temp],((float)(time_tick()-time))/100);
  465. #else
  466.     if((time_tick()-time) < 2990)
  467.         printf("I moved at %c %d in %5.2f seconds\n",
  468.             'a'+j_tran[temp],1+i_tran[temp],((float)(time_tick()-time))/100);
  469.     else
  470.         printf("I moved at %c %d in 29.52 seconds\n",
  471.             'a'+j_tran[temp],1+i_tran[temp]);
  472. #endif
  473.  
  474.     putboard((*board),(*board)->sons[bestboard]);
  475.  
  476. #if DEBUG_LEVEL > 1
  477.     if((time_tick()-time) > 3000)
  478.         printf("\7\7\7\7\7\7");
  479.     printf("movenumber: %d choices: %d depth: %d",
  480.             movenumber,n,maxdepth[movenumber]);
  481. #if DEBUG_LEVEL > 2
  482.     printf(" boards available: %d",count_boards()+n);
  483. #endif
  484.     printf("\nallsons called: %d worth called: %d boards used: %d\n",
  485.             allsons_called,worth_called,max_used_boards);
  486.     printf("  alpha prunes: %d  beta prunes: %d       total: %d",
  487.             alpha_prunes,beta_prunes,alpha_prunes+beta_prunes);
  488.     printf(" max branching: %d\n",greatest_branching);
  489. #endif
  490.  
  491.     /* now reclaim unneeded boards, reset the root, and count this move */
  492.     for(i=0;i<n;i++)
  493.         if(i!=bestboard)
  494.             reclaim((*board)->sons[i]);
  495.     tempboard=(*board)->sons[bestboard];
  496.     reclaim(*board);
  497.     *board=tempboard;
  498.     movenumber++;
  499. }
  500.  
  501. /*
  502.     alphabeta takes four parameters: the board to evaluate,
  503.     the depth to search, and the current alpha and beta values.
  504.     It returns the worth of the board, obtained by backing up
  505.     the values seen at the bottom of the search.
  506.     It plays maximizing or minimizing, based on the global
  507.     boolean variable max.
  508. */
  509.     
  510. int alphabeta(current,depth,alpha,beta)
  511. BOARD *current;
  512. int depth,
  513.     alpha,
  514.     beta;
  515. {
  516.     int i,
  517.         n,
  518.         temp,
  519.         best,
  520.         curmax;     /* contains the current value of the global "max",    */
  521.                     /* negated (to minimize the number of negations)    */
  522.  
  523.     BOARD *curson;    /* contains the son being examined currently        */
  524.  
  525.     /* if no sons can be found */
  526.     if(!(n=allsons(current)))
  527.     {
  528.         max=!max;                        /* then try as the other guy    */
  529.         if(!(n=allsons(current)))        /* and if he can't move            */
  530.             return(worth_2(current));    /* return the final value        */
  531.     }
  532.  
  533.     best=max?WORST:BEST;    /* start off assuming the worst     */
  534.     depth--;                /* keep track of depth                */
  535.     curmax=!max;            /* and max through recursive calls    */
  536.  
  537.     /* for every son */
  538.     for(i=0;i<n;i++)
  539.     {
  540.         max=curmax;
  541.         curson=current->sons[i];
  542.  
  543.         /*
  544.             This statement does it all. Recurse, propogating correct alpha
  545.             and beta values (only one of which can change at any given node)
  546.             unless of course the recursion has terminated, in which case we
  547.             use the value of the node, as evaluated by worth when allsons
  548.             created the node. Put the value thus obtained into temp, and
  549.             compare it with the best value seen so far. The sense of
  550.             comparison is reversed if curmax is true (bitwise xor is all
  551.             right if both booleans are "pure"--0 or 1).
  552.         */
  553.         if(curmax^best<(temp=depth?
  554.                                 (curmax?
  555.                                     alphabeta(curson,depth,alpha,best)
  556.                                     :alphabeta(curson,depth,best,beta))
  557.                                 :curson->val))
  558.         {
  559.             /* check for an alphabeta "prune" of the tree */
  560.             if(curmax?(temp<=alpha):(temp>=beta))
  561.             {
  562.  
  563. #if DEBUG_LEVEL > 1
  564.                 if(curmax)
  565.                     beta_prunes++;
  566.                 else                /* accumulate statistics */
  567.                     alpha_prunes++;
  568. #endif
  569.  
  570.                 while(i<n)                        /* clean up            */
  571.                     reclaim(current->sons[i++]);
  572.                 return(temp);                    /* and pack it in    */
  573.             }
  574.             else
  575.                 best=temp;    /* remember the best value seen so far    */
  576.         }
  577.         reclaim(curson);
  578.     }
  579.     return(best);
  580. }
  581.  
  582. /*
  583.     Simple-minded free space management. Keep a bunch of boards on a linked
  584.     list. When one is needed, take it off the top. When no longer needed,
  585.     insert it at the top. Optionally, check for out-of-boards (The converse,
  586.     attempting to check for freeing of space not taken from the freeboard
  587.     list, seemed to be too difficult. Perhaps I could have kept around high-
  588.     water and low-water mark pointers to the space of legal board pointers.),
  589.     and accumulate statistics.
  590. */
  591.  
  592. BOARD *newboard()
  593. {
  594.     BOARD *temp;
  595.  
  596. #if DEBUG_LEVEL > 0
  597.     if(!freeboards)
  598. #if DEBUG_LEVEL > 1
  599.     {
  600.         printf("Gotta grab more boards...\n");
  601.         printf("Current boards outstanding : %d\n",boards_in_use);
  602.         printf("           High-water mark : %d\n",max_used_boards);
  603. #endif
  604.         initfree();
  605. #if DEBUG_LEVEL > 1
  606.     }
  607.  
  608.     boards_in_use++;
  609.     if(max_used_boards<boards_in_use)
  610.         max_used_boards=boards_in_use;
  611. #endif
  612. #endif
  613.  
  614.     temp=freeboards;
  615.     freeboards=freeboards->sons[0];
  616.     temp->sons[0]=NULL;
  617.     return(temp);
  618. }
  619.  
  620. reclaim(board)
  621. BOARD *board;
  622. {
  623. #if DEBUG_LEVEL > 1
  624.     boards_in_use--;
  625. #endif
  626. #if DEBUG_LEVEL > 2
  627.     if(board<board_bottom || board > board_end)
  628.         printf("warning: attempted to reclaim non-board\n");
  629.     else
  630.     {
  631. #endif
  632.  
  633.     board->sons[0]=freeboards;
  634.     freeboards=board;
  635.  
  636. #if DEBUG_LEVEL > 2
  637.     }
  638. #endif
  639.  
  640. }
  641.  
  642. /*
  643.     Shell sort taken from K&R, sorts the n boards in the array into ascending
  644.     or descending order based on the global boolean max, sorting on the
  645.     values contained in the value member of each board structure. This sort
  646.     focuses the alphabeta search significantly, increasing the pruning enough
  647.     to cut depth 4 search time by approximately 65 percent.
  648. */
  649.  
  650. sort(boards,n)
  651. BOARD **boards;
  652. int n;
  653. {
  654.     int i,
  655.         j,
  656.         gap,
  657.         jpg; /* temporary storage hold j+gap */
  658.  
  659.     BOARD *tempboard;
  660.  
  661.     for(gap=n/2;gap>0;gap/=2)
  662.         for(i=gap;i<n;i++)
  663.             for(j=i-gap;j>=0 &&
  664.                     (max?(boards[j]->val<boards[jpg=j+gap]->val):
  665.                     (boards[j]->val>boards[jpg=j+gap]->val));j-=gap)
  666.             {
  667.                 tempboard=boards[j];
  668.                 boards[j]=boards[jpg];
  669.                 boards[jpg]=tempboard;
  670.             }
  671. }
  672.  
  673. /*
  674.     Initialize a linked list of free boards. Each board has an array of
  675.     8 pointers to rows of 8 bytes each. Allocate space for the rows, and
  676.     initialize the pointer arrays to point to the rows. The rows in a board
  677.     are explicitly allocated contiguously, so it is possible (and turns out
  678.     to enhance efficiency at the expense of comprehensability) to treat
  679.     a board as a single array of 64 bytes, pointed to by the pointer to
  680.     the first row. Optionally, produce statistics on allocation of memory.
  681. */
  682.  
  683. initfree()
  684. {
  685.     int i,j;
  686.  
  687.     char *calloc(),
  688.          *boardspace;
  689.  
  690.     freeboards=((BOARD *) calloc(maxboards,sizeof(BOARD)));
  691.     if(!freeboards)
  692.     {
  693.         printf("The board structure allocation failed. Sorry, boss.\n");
  694.         exit(0);
  695.     }
  696.     boardspace=calloc(maxboards,sizeof(char [64]));
  697.     if(!boardspace)
  698.     {
  699.         printf("The board freespace allocation failed. Sorry, boss.\n");
  700.         exit(0);
  701.     }
  702.  
  703. #if DEBUG_LEVEL > 1
  704.     printf("    board  space %u\n",((unsigned int) freeboards));
  705.     printf("            thru %u\n",
  706.             ((unsigned int) (freeboards+maxboards)));
  707.     printf("    board arrays %u\n",((unsigned int) boardspace));
  708.     printf("            thru %u\n",
  709.             ((unsigned int) (boardspace+64*maxboards)));
  710. #endif
  711.  
  712.     /* thread linked list and arrange the row pointer arrays */
  713.     for(i=0;i<maxboards;i++)
  714.     {
  715.         freeboards[i-1].sons[0]=freeboards+i;
  716.         for(j=0;j<8;j++)
  717.             freeboards[i].array[j]=boardspace+64*i+8*j;
  718.     }
  719.     freeboards[maxboards-1].sons[0]=NULL;
  720.  
  721. #if DEBUG_LEVEL > 2
  722.     board_end=freeboards+(maxboards-1);
  723.     board_count+=maxboards;
  724. #endif
  725.  
  726.     /* We might be called again, if he needs more boards */
  727.     maxboards=10;
  728. }
  729.  
  730. /*
  731.     The array moves contains information about the shape of a board, in
  732.     a fashion which simplifies the checking of loop conditions in the
  733.     code which is examining a board for a move, and flipping the resulting
  734.     pieces. Specifically, moves (which is a byte array because it needs
  735.     no large numbers) is used as follows:
  736.         moves[i][j][k] refers to the subscript of the
  737.             k-th square, in the
  738.             j-th direction, from the
  739.             i-th square on the board.
  740.     Moves is 64 long; moves[i] is variable length delimited by NULL; and
  741.     moves[i][j] is variable length delimited by the value of i.
  742. */
  743.  
  744. initmoves()
  745. {
  746.     int i,
  747.         j,
  748.         k,
  749.         l,
  750.         m,
  751.         n;
  752.  
  753.     char *calloc(),
  754.          **pointers,
  755.          *bytes;
  756.  
  757.     /* 484 and 2016 are computed by rote */
  758.     pointers=((char **) calloc(484,sizeof(char **)));
  759.     if(pointers==NULL)
  760.     {
  761.         printf("initmoves: cannot allocate pointers. Sorry, boss.\n");
  762.         exit(0);
  763.     }
  764.     bytes=calloc(2016,sizeof(char));
  765.     if(bytes==NULL)
  766.     {
  767.         printf("initmoves: cannot allocate bytes. Sorry, boss.\n");
  768.         exit(0);
  769.     }
  770.  
  771. #if DEBUG_LEVEL > 1
  772.     printf("pointers  set to  %u\n",((unsigned int) pointers));
  773.     printf("   bytes  set to  %u\n",((unsigned int) bytes));
  774. #endif
  775.  
  776.     /* for each square on the board */
  777.     for(i=0;i<8;i++) for(j=0;j<8;j++)
  778.     {
  779.  
  780.         /* set the corresponding entry of moves to some free pointers */
  781.         moves[i*8+j]=pointers;
  782.  
  783.         /* for each direction */
  784.         for(k=(-1);k<2;k++) for(l=(-1);l<2;l++)
  785.             if(k || l)    /* if neither k or l we aren't going anywhere */
  786.             {
  787.                 *pointers=bytes; /* point to some free bytes */
  788.                 /* let m and n walk to the edge of the board */
  789.                 for(m=i+k,n=j+l;m>=0 && m<8 && n>=0 && n<8;m+=k,n+=l)
  790.                     (*bytes++)=m*8+n;
  791.                 if(m!=i+k || n!=j+l)
  792.                 /* then we managed to walk somewhere */
  793.                 {
  794.                     (*bytes++)=i*8+j;    /* terminate bytes list                */
  795.                     pointers++;            /* get pointer for next direction    */
  796.                 }
  797.             }
  798.         (*pointers++)=NULL;    /* terminate pointers list */
  799.     }
  800.  
  801. #if DEBUG_LEVEL > 1
  802.     printf("pointers left at %u\n",((unsigned int) pointers));
  803.     printf("   bytes left at %u\n",((unsigned int) bytes));
  804. #endif
  805.  
  806. }
  807.  
  808. #if DEBUG_LEVEL > 2
  809. int check_moves()
  810. {
  811.     int i,
  812.         chk1,
  813.         chk2;
  814.  
  815.     char **ptr1,
  816.          *ptr2;
  817.  
  818.     chk1=chk2=0;
  819.     for(i=0;i<64;i++)
  820.         for(ptr1=moves[i];*ptr1;ptr1++)
  821.             for(ptr2=(*ptr1);(*ptr2)!=i;ptr2++)
  822.             {
  823.                 if(*ptr2<0 || *ptr2>63)
  824.                     printf("moves subscript out of range at i=%d sub=%d\n\7",i,*ptr2);
  825.                 chk2+=chk1^=(*ptr2);
  826.             }
  827.     return(chk1+chk2);
  828. }
  829.  
  830. int count_boards()
  831. {
  832.     int i;
  833.  
  834.     BOARD *ptr;
  835.  
  836.     for(i=0,ptr=freeboards;ptr;i++,ptr=ptr->sons[0]);
  837.     return(i);
  838. }
  839. #endif
  840.  
  841. /*
  842.     allsons finds all sons for the board which is its parameter, sets the
  843.     array of pointers to sons to point to new boards containing the resulting
  844.     boards, sets the val member of each son board structure to the value as
  845.     evaluated by worth, and sorts the sons in order, to focus the alphabeta
  846.     search. It returns the number of sons it found.
  847. */
  848.  
  849. int allsons(pos)
  850. BOARD *pos;
  851. {
  852.     int cur=0, /* son next to allocate */
  853.         i;
  854.  
  855.     char mine,            /* mine, from the point of the current player    */
  856.          hisn,            /* likewise                                        */
  857.          whose,            /* temporary variable--keep from recomputing    */
  858.          *board,        /* pointer into the board array                    */
  859.          ***move_ptr,    /* pointer into the moves array                    */
  860.          **dir_ptr,        /* pointer into moves[i] arrays of directions    */
  861.          *sub_ptr;        /* pointer into moves[i][j] arrays of subscrtips*/
  862.  
  863.     BOARD *resultof(),    /* create a board resulting from making a move    */
  864.           *curson;        /* point to current son                            */
  865.  
  866. #if DEBUG_LEVEL > 1
  867.     allsons_called++;
  868. #endif
  869.  
  870.     mine=max?MINE:HIS;
  871.     hisn=max?HIS:MINE;
  872.     board=pos->array[0];
  873.  
  874.     /* for(i=0;i<64;i++) with move_ptr=moves[i] */
  875.     for(i=0,move_ptr=moves;i<64;i++,move_ptr++)
  876.     {
  877.         /* if(board[i]==EMPTY) */
  878.         if(!board[i])
  879.             /* for(j=0;moves[i][j]!=NULL;j++) with sub_ptr=moves[i][j] */
  880.             for(dir_ptr=(*move_ptr);sub_ptr=(*dir_ptr++);)
  881.                 /* if he owns the cell in the j-th direction */
  882.                 if(board[*sub_ptr++]==hisn)
  883.                 {
  884.                     /* scan until edge of board or end of list */
  885.                     /*
  886.                         NOTE: moves[i][j] is delimited by i, so the edge of
  887.                         the board looks like a cell containing the same thing
  888.                         as board[i], which must be empty if I got into this
  889.                         code; therefore, hitting edge of board looks just
  890.                         like seeing a space at the end of the string of
  891.                         opponents pieces, which means I cannot capture them.
  892.                     */
  893.                     while((whose=board[*sub_ptr++])==hisn);
  894.                     if(whose==mine) /* then we have a possible capture */
  895.                     {
  896.                         curson=pos->sons[cur++]=resultof(pos,i);
  897.                         curson->val=(*worth)(curson);
  898.                         goto endit;    /* don't look in other directions */
  899.                     }
  900.                 }
  901. endit:    ;
  902.     }
  903.  
  904. #if DEBUG_LEVEL > 0
  905.     if(cur>MAXSONS)
  906.     {
  907.         fprintf(stderr,"allsons: I needed %d sons for",cur+1);
  908.         putboard(pos,NULL);
  909.         fprintf(stderr,"allsons: but I only am alotted %d.\n",MAXSONS);
  910.         printf("Sorry, boss.\n");
  911.         exit(0);
  912.     }
  913. #endif
  914. #if DEBUG_LEVEL > 1
  915.     if(greatest_branching < cur)
  916.         greatest_branching=cur;
  917. #endif
  918.  
  919.     sort(pos->sons,cur);
  920.     pos->sons[cur]=0;
  921.     return(cur);
  922. }
  923.  
  924. /*
  925.     Resultof makes a copy of the board (using _move(), a fast block
  926.     move routine that comes with Mark DeSmet's Cware C compiler, if
  927.     the code is being generated for an IBM-PC) and flips all squares
  928.     thet need to be flipped based on making a move at position x
  929.     (where x ranges for 0 to 63), takes the square at x, and returns
  930.     a pointer to the resulting board. It calls newboard(), the free
  931.     board server.
  932. */
  933.  
  934. BOARD *resultof(father,x)
  935. BOARD *father;
  936. int x;
  937. {
  938.     int mine,    /* mine, from the point of view of the current player    */
  939.         hisn;    /* likewise                                                */
  940.  
  941.     char *board,    /* pointer into the board array                        */
  942.  
  943. #ifndef IBMPC
  944.          *tmpptr,    /* pointers for copying the board in portble C        */
  945.          *tmplim,
  946. #endif
  947.  
  948.          **dir,    /* pointer for moves[x][j], a direction                    */
  949.          *sub;    /* pointer to a subscript, moves[i][j][k]                */
  950.  
  951.     BOARD *newboard(),
  952.           *temp;
  953.  
  954.     mine=max?MINE:HIS;
  955.     hisn=max?HIS:MINE;
  956.     temp=newboard();
  957.  
  958.     /* Copy the board. Use a block move on the PC    */
  959. #ifdef IBMPC
  960.     _move(64,father->array[0],temp->array[0]);
  961. #else
  962.     board=temp->array[0];
  963.     tmpptr=father->array[0];
  964.     tmplim=board+64;
  965.     while(board<tmplim)
  966.         (*board++)=(*tmpptr++);
  967. #endif
  968.  
  969.     board=temp->array[0];
  970.  
  971.     /* for(j=0;moves[x][j]!=NULL;j++) */
  972.     for(dir=moves[x];*dir;dir++)
  973.         /* if the cell in the j-th direction is his  */
  974.         if(board[**dir]==hisn)
  975.         {
  976.             sub=(*dir);
  977.  
  978.             /* scan as long as the pieces are his    */
  979.             /* (Please see discussion in allsons    */
  980.             while(board[*++sub]==hisn);
  981.  
  982.             /* if the search was terminated by a piece of mine */
  983.             if(board[*sub]==mine)
  984.             {
  985.                 /* do the same scan, flipping pieces as you go */
  986.                 sub=(*dir);
  987.                 while(board[*sub]==hisn)
  988.                     board[*(sub++)]=mine;
  989.             }
  990.         }
  991.  
  992.     /* put a piece where we actually moved */
  993.     board[x]=mine;
  994.     return(temp);
  995. }
  996.  
  997. /*
  998.     firstboard() returns a pointer to a board set up in the initial position.
  999.     It is the only routine that actually zeros out a board array, and sets
  1000.     things up in it. The remainder of the boards are made by copying and
  1001.     then changing, by resultof(). The initial position is reversed if we
  1002.     are going first (because what is stored is not x's and o's, but MINE
  1003.     and HIS) and can be reversed again by a reverse switch.
  1004. */
  1005.  
  1006. BOARD *firstboard()
  1007. {
  1008.     BOARD *temp,
  1009.           *newboard();
  1010.  
  1011.     int i,
  1012.         j;
  1013.  
  1014.     temp=newboard();
  1015.  
  1016.     /* zero out the array */
  1017.     for(i=0;i<8;i++)
  1018.         for(j=0;j<8;j++)
  1019.             temp->array[i][j]=EMPTY;
  1020.     /* put the start position into the cells */
  1021.     /* either gofirst or reversed can switch the initialization */
  1022.     temp->array[3][3]=temp->array[4][4]=(!(gofirst^reversed))?MINE:HIS;
  1023.     temp->array[3][4]=temp->array[4][3]=(!(gofirst^reversed))?HIS:MINE;
  1024.  
  1025. #if DEBUG_LEVEL > 1
  1026.     temp->val=0;
  1027. #endif
  1028.  
  1029.     return(temp);
  1030. }
  1031.  
  1032. /*
  1033.     Getmove gets a move from the user. If the computer is an IBM-PC,
  1034.     the result is immediately displayed; otherwise, the user must wait
  1035.     for the computer to move. This is because of timing considerations;
  1036.     dumping a board into the video ram takes very little time, while
  1037.     cramming it through a 1200 baud line takes a fair while.
  1038.     There is complete checking for invalid input, but no verify or revise
  1039.     option (typo's will hurt you if they are legal moves).
  1040. */
  1041.  
  1042. getmove(board)
  1043. BOARD **board;
  1044. {
  1045.     int i,
  1046.         j,
  1047.         k,
  1048.         n;
  1049.  
  1050.     char ans;
  1051.  
  1052.     BOARD *resultof(),
  1053.           *temp;
  1054.  
  1055.     long time_tick();
  1056.  
  1057.     max=FALSE;
  1058.  
  1059.     /* if(<the number of sons found>==0) */
  1060.     if(!(n=allsons(*board)))
  1061.     {
  1062.         printf("You cannot move. My turn. Press return to continue: ");
  1063.  
  1064. #ifdef DeSmet
  1065.         scanf("\n");
  1066. #else
  1067.         while(getchar()!='\n');
  1068. #endif
  1069.  
  1070.         time=time_tick();
  1071.         return;
  1072.     }
  1073.  
  1074.     movenumber++;
  1075.     if(n==1)
  1076.     {
  1077.         printf("You have only one move. Press return to continue: ");
  1078.  
  1079. #ifdef DeSmet
  1080.         scanf("\n");
  1081. #else
  1082.         while(getchar()!='\n');
  1083. #endif
  1084.  
  1085.         time=time_tick();
  1086.         temp=(*board)->sons[0];
  1087.  
  1088. #if DEBUG_LEVEL > 1
  1089.         temp->val=worth(temp);
  1090. #endif
  1091.  
  1092. #ifdef IBMPC
  1093.         line_number=BOARD_TOP;
  1094.         putboard(temp,(*board));
  1095. #endif
  1096.  
  1097.         reclaim(*board);
  1098.         (*board)=temp;
  1099.         return;
  1100.     }
  1101.  
  1102.     /* get and validity check move */
  1103. retry:
  1104.     printf("Please input next move: ");
  1105.     scanf("%c%d",&ans,&i);
  1106.     time=time_tick();
  1107.  
  1108. #ifndef DeSmet
  1109.     while(getchar()!='\n');
  1110. #endif
  1111.  
  1112.     i--;
  1113.     j=tolower(ans)-'a';
  1114.     /* if(<position is out of range> || board[i][j]!=EMPTY) */
  1115.     if(i<0 || i>7 || j<0 || j>7 || (*board)->array[i][j])
  1116.     {
  1117.         printf("try again, numbnut.\n");
  1118.         goto retry;
  1119.     }
  1120.     /* scan the sons list, looking for a son with this cell occupied    */
  1121.     for(k=0;!((*board)->sons[k]->array[i][j]);)
  1122.         /* if we have reached the end of the list without finding one    */
  1123.         if(++k==n)
  1124.         {
  1125.             printf("try again, numbnut.\n");
  1126.             goto retry;
  1127.         }
  1128.  
  1129.     /* clean up stray sons */
  1130.     for(i=0;i<n;i++)
  1131.         if(i!=k)
  1132.             reclaim((*board)->sons[i]);
  1133.     temp=(*board)->sons[k];
  1134.  
  1135. #if DEBUG_LEVEL > 1
  1136.     temp->val=worth(temp);
  1137. #endif
  1138.  
  1139. #ifdef IBMPC
  1140.     line_number=BOARD_TOP;
  1141.     putboard(temp,(*board));
  1142. #endif
  1143.  
  1144.     reclaim(*board);
  1145.     *board=temp;
  1146. }
  1147.  
  1148. /*
  1149.     Score simply adds up the number of cells owned by each player,
  1150.     reports the results, and leaves.
  1151. */
  1152.  
  1153. score(board)
  1154. BOARD *board;
  1155. {
  1156.     char i,
  1157.          sums[3]={0,0,0},
  1158.          *ptr;
  1159.  
  1160.     ptr=board->array[0];
  1161.     for(i=0;i<64;i++)
  1162.         sums[*ptr++]++;
  1163.     printf("I got %d; You got %d; %s.\n",sums[MINE],sums[HIS],
  1164.             sums[MINE]>sums[HIS]?"I win":
  1165.             (sums[MINE]==sums[HIS]?"The game is a draw":"You win"));
  1166. }
  1167.  
  1168. #ifdef IBMPC
  1169.  
  1170. /*
  1171.     Fast output routines for the IBM-PC. These use _lmove(), an intersegment
  1172.     block move subroutine that comes with the DeSmet C compiler.
  1173.  
  1174.     Fast_puts(s) moves the string which is its operand, delimited by
  1175.     return, newline, NULL, or any other non-printing character, and puts
  1176.     it into the video ram.
  1177. */
  1178.  
  1179. fast_puts(s)
  1180. char *s;
  1181. {
  1182.     int i;
  1183.  
  1184.     /*
  1185.         since the character bytes in the video ram are interleaved with
  1186.         attribute bytes:
  1187.         for(i=0;s[i]>'\n';i++)
  1188.             scr_line[2*i]=s[i];
  1189.     */
  1190.     for(i=0;(scr_line[i<<1]=s[i])>'\n';i++);
  1191.  
  1192.     /* and pad with blanks */
  1193.     while(i<80)
  1194.         scr_line[i++<<1]=' ';
  1195.     /* now shove the line out, pronto */
  1196.     _lmove(160,scr_line,_showds(),line_number,screen_seg);
  1197.     /* increment the video ram line offset */
  1198.     line_number+=160;
  1199. }
  1200.  
  1201. /* clear the top part of the screen, and home the cursor */
  1202. clear_home()
  1203. {
  1204.     int i;
  1205.  
  1206.     /* make a blank video line */
  1207.     for(i=0;i<80;scr_line[i++<<1]=' ');
  1208.  
  1209.     /* and run it out */
  1210.     for(line_number=0;line_number<BOARD_TOP;line_number+=160)
  1211.         _lmove(160,scr_line,_showds(),line_number,screen_seg);
  1212.  
  1213. #asm
  1214.     mov    ah,15    ; function number to read video page
  1215.     int    10h        ; rom bios call to make a video function request
  1216.     mov    dx,0    ; dh=dl=0 for top right-hand corner
  1217.     mov    ah,2    ; function number for cursor positioning
  1218.     int    10h        ; rom bios call to make a video function request
  1219. #
  1220. }
  1221.  
  1222. /*
  1223.     Grab a representative line out of the video ram, to get the current
  1224.     attribute bytes.
  1225. */
  1226.  
  1227. init_screen()
  1228. {
  1229.     int monochrome;
  1230.  
  1231. #asm
  1232.     push    ds            ; save data segment
  1233.     mov        ax,40h        ; load hex 40
  1234.     mov        ds,ax        ; into data segment
  1235.     mov        di,[10h]    ; get equipment flags
  1236.     pop        ds            ; restore data segment
  1237.     and        di,30h        ; check for monochrome board
  1238.     mov        [bp-2],di    ; put value in local monochrome
  1239. #
  1240.     screen_seg=(monochrome==0x30)?0xb000:0xb800;
  1241.     _lmove(160,0,screen_seg,scr_line,_showds());
  1242. }
  1243.  
  1244. #else
  1245.  
  1246. /*
  1247.     by careful design, fast_puts() is functionally equivalent to printf
  1248. */
  1249.  
  1250. #define fast_puts printf
  1251.  
  1252. #endif
  1253.  
  1254. /*
  1255.     Putboard can be used for one or two boards. For one board, make the
  1256.     second parameter NULL. It calls a function fast_puts to put the string
  1257.     out. This is to allow quick board drawing on a PC.
  1258.     Optionally, error checking code can be compiled in, to check for the
  1259.     (common) C bug of wandering of into randomn memory locations.
  1260.     Throughout the function, realize the "if(new)" is functionally identical
  1261.     to "if(new!=NULL)".
  1262. */
  1263.  
  1264. putboard(old,new)
  1265. BOARD *old,
  1266.       *new;
  1267. {
  1268.     int i,
  1269.         j,
  1270.         k;
  1271.  
  1272.     char s[80];
  1273.  
  1274. #ifdef IBMPC
  1275.     line_number=BOARD_TOP; /* offset of top of board */
  1276. #endif
  1277.  
  1278.     if(new)
  1279.         fast_puts("      a   b   c   d   e   f   g   h        a   b   c   d   e   f   g   h\n");
  1280.     else
  1281.         fast_puts("      a   b   c   d   e   f   g   h\n");
  1282.  
  1283.     /* for every row */
  1284.     for(i=0;i<8;i++)
  1285.     {
  1286.         k=0;
  1287.         if(new)
  1288.             fast_puts("    ---------------------------------    ---------------------------------\n");
  1289.         else
  1290.             fast_puts("    ---------------------------------\n");
  1291.         sprintf(s,"  %d | ",i+1);
  1292.         while(s[++k]);
  1293.  
  1294.         /* for every column in the first board */
  1295.         for(j=0;j<8;j++)
  1296.         {
  1297.  
  1298. #if DEBUG_LEVEL > 0
  1299.             if(old->array[i][j]<0 || old->array[i][j]>2)
  1300.             {
  1301.                 printf("putboard: garbage in cell %d %d--exiting...\n",i,j);
  1302.                 exit(0);
  1303.             }
  1304. #endif
  1305.  
  1306.             s[k++]=print_chars[old->array[i][j]];
  1307.             s[k++]=' ';
  1308.             s[k++]='|';
  1309.             s[k++]=' ';
  1310.         }
  1311.  
  1312.         if(new)
  1313.         {
  1314.             sprintf(s+k," %d | ",i+1);
  1315.             while(s[++k]);
  1316.  
  1317.             /* for every column in the second board */
  1318.             for(j=0;j<8;j++)
  1319.             {
  1320.  
  1321. #if DEBUG_LEVEL > 0
  1322.                 if(new->array[i][j]<0 || old->array[i][j]>2)
  1323.                 {
  1324.                     printf("putboard: garbage in cell %d %d--exiting...\n",i,j);
  1325.                     exit(0);
  1326.                 }
  1327. #endif
  1328.  
  1329.                 s[k++]=print_chars[new->array[i][j]];
  1330.                 s[k++]=' ';
  1331.                 s[k++]='|';
  1332.                  s[k++]=' ';
  1333.             }
  1334.  
  1335.         }
  1336.         s[k++]='\n';
  1337.         s[k]='\0';
  1338.         fast_puts(s);
  1339.     }
  1340.  
  1341.     if(new)
  1342.         fast_puts("    ---------------------------------    ---------------------------------\n");
  1343.     else
  1344.         fast_puts("    ---------------------------------\n");
  1345.  
  1346. #if DEBUG_LEVEL > 1
  1347.     if(new)
  1348.         sprintf(s,"                  %d                                     %d\n",
  1349.                 old->val,new->val);
  1350.     else
  1351.         sprintf(s,"                  %d\n",old->val);
  1352.     fast_puts(s);
  1353. #endif
  1354. }
  1355.  
  1356. /*
  1357.     Worth_1 is the worth function containing all the subtle strategic
  1358.     heuristic information in the game. It is used until we can start
  1359.     looking all the way to the end of the game, at which point the
  1360.     optimum heuristic function, h* becomes available. That is called
  1361.     worth_2, and is much simpler.
  1362. */
  1363.  
  1364. worth_1(board)
  1365. BOARD *board;
  1366. {
  1367.     int valsum[3]; /* buckets in which to accumulate the sums        */
  1368.  
  1369.     char *ptr,    /* temporary pointers for walking through the array    */
  1370.          *t;
  1371.  
  1372.     static char
  1373.         val1[3]={30,0,0},    /* value of (1,1) if (0,0)=0,1,2 */
  1374.         val2[3]={ 4,0,0},    /* value of (1,2) if (0,2)=0,1,2 */
  1375.         val3[3]={ 5,0,0};    /* value of (1,3) if (0,3)=0,1,2 */
  1376.  
  1377. #define ev0    50    /* value of pos 00 (corner)        */
  1378. #define ev1    4    /* value of pos 01                */
  1379. #define ev2    16    /* value of pos 02                */
  1380. #define ev3    12    /* value of pos 03                */
  1381. #define sv    20    /* value of a split on the edge */
  1382.  
  1383. /*
  1384.      50,  4, 16, 12, 12, 16,  4, 50,
  1385.       4,-30, -4, -5, -5, -4,-30,  4,
  1386.      16, -4,  1,  0,  0,  1, -4, 16,        This is what the board cell
  1387.      12, -5,  0,  0,  0,  0, -5, 12,        worth function looks like,
  1388.      12, -5,  0,  0,  0,  0, -5, 12,        discounting all dynamic
  1389.      16, -4,  1,  0,  0,  1, -4, 16,        dependancies.
  1390.       4,-30, -4, -5, -5, -4,-30,  4,
  1391.      50,  4, 16, 12, 12, 16,  4, 50
  1392. */
  1393.  
  1394. /*
  1395.     f[] is a finite state automaton used for edge strategy
  1396.     It recognizes two related phenomena, which we call "splits";
  1397.     positions where two pieces owned by one player on an edge are
  1398.  
  1399.         a) separated by exactly 1 blank, or
  1400.         b) separated by 1 or more of the opponent's
  1401.  
  1402.     Invented by John White, it is structured as follows:
  1403.  
  1404.     f[105] can be viewed as 5 tiers of 7 states, each of which requires
  1405.     3 cells for the three possible input values.
  1406.     Starting at one corner, you scan along an edge.
  1407.     Keep always in mind that the values of board cells are
  1408.  
  1409.                         0        EMPTY
  1410.                         1        MINE
  1411.                         2        HIS
  1412.  
  1413.     The states are numbered as follows:
  1414.  
  1415.       state            decription                        board
  1416.       -----    ----------------------------------        ------
  1417.  
  1418.         0    currently scanning through blanks        ... 0
  1419.         1    just seen a square of mine                ... 1
  1420.         2    just seen a square if his                ... 2
  1421.         3    a blank following a square of mine        ... 10
  1422.         4    a blank following a square of his        ... 20
  1423.         5    one of his following one of mine        ... 12
  1424.         6    one of mine following one of his        ... 21
  1425.  
  1426.     The following table identifies the transitions between states.
  1427.     The numbers down the left, labelling the rows, are the input
  1428.     cell values. The numbers across the top are state numbers.
  1429.     The contents of a cell in this matrix is the number of the
  1430.     state the will be result from the input at the left from the
  1431.     state above.
  1432.  
  1433.             0        1        2        3        4        5        6
  1434.         ---------------------------------------------------------
  1435.     0    |    0    |    3    |    4    |    0    |    0    |    4    |    3    |
  1436.         ---------------------------------------------------------
  1437.     1    |    1    |    1    |    6    |    1 -    |    1    |    6 -    |    6    |
  1438.         ---------------------------------------------------------
  1439.     2    |    2    |    5    |    2    |    2    |    2 +    |    5    |    5 +    |
  1440.         ---------------------------------------------------------
  1441.  
  1442.     The cells containing postfix "+" or "-" symbols represent
  1443.     situations in which we have found one of the key patterns,
  1444.     at which point we go to the state indicated in the immediately
  1445.     higher or lower tier, respectively. The final value is
  1446.     simply the number of the tier we are on at the end, multiplied
  1447.     by sv, the split value. Note that each state takes three array elements,
  1448.     so the actual contents of the array are three times the state
  1449.     numbers shown above, repeated 5 times, offset by the tier start
  1450.     subscripts, with special offsets applied to the cells which
  1451.     jump tiers. The array v[] is used for the last lookup, since
  1452.     we are uninterested in the exact state, but just the tier, and
  1453.     since the tier number must be multiplied by sv, we put the resulting
  1454.     products in v[]. Finally, the tiers are organized as follows:
  1455.  
  1456.               offset    meaning                value
  1457.               ------ ----------------        -----
  1458.         
  1459.                  0         neutral               0
  1460.                 21          good                  sv
  1461.                 42          bad                 -sv
  1462.                 63        very good             2*sv
  1463.                 84        very bad            -2*sv
  1464.  
  1465.     With this organization, if the state of the machine at time t0 is
  1466.     S0 and the input is I0, the state at time t1 is f[S0+I0], and therefore
  1467.     the state at time t2 is f[f[S0+I0]+I1] and so forth.
  1468.     So, without further ado:
  1469. */
  1470.  
  1471.     static char f[105]=
  1472.                 {
  1473. /*----------------------------------------------------------------------------
  1474. |state    0             1           2         3           4          5             6   |
  1475. |input 0  1  2   0  1  2   0   1  2   0  1  2   0  1  2   0   1  2   0   1  2|
  1476. ----------------------------------------------------------------------------*/
  1477.        0, 3, 6,  9, 3,15, 12, 18, 6,  0,45, 6,  0, 3,27, 12, 60,15,  9, 18,36,
  1478.       21,24,27, 30,24,36, 33, 39,27, 21, 3,27, 21,24,69, 33, 18,36, 30, 39,78,
  1479.       42,45,48, 51,45,57, 54, 60,48, 42,87,48, 42,45, 6, 54,102,57, 51, 60,15,
  1480.       63,66,69, 72,66,78, 75, 81,69, 63,24,69, 63,66,69, 75, 39,78, 72, 81,78,
  1481.       84,87,90, 93,87,99, 96,102,90, 84,87,90, 84,87,48, 96,102,99, 93,102,57
  1482.                 };
  1483.  
  1484. /* v is the final pass of f, and is board value instead of next state */
  1485.  
  1486.     static int v[105]=
  1487.                {
  1488.         0,0,0,0,0,0,0,0,0,0,-sv,0,0,0,sv,0,-sv,0,0,0,sv,
  1489.         sv,sv,sv,sv,sv,sv,sv,sv,sv,sv,0,sv,sv,sv,2*sv,sv,0,sv,sv,sv,2*sv,
  1490.         -sv,-sv,-sv,-sv,-sv,-sv,-sv,-sv,-sv,-sv,-2*sv,-sv,-sv,-sv,0,-sv,
  1491.                 -2*sv,-sv,-sv,-sv,0,
  1492.         2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,2*sv,sv,2*sv,2*sv,
  1493.                 2*sv,2*sv,2*sv,sv,2*sv,2*sv,2*sv,2*sv,
  1494.         -2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,
  1495.                 -2*sv,-2*sv,-2*sv,-sv,-2*sv,-2*sv,-2*sv,-2*sv,-2*sv,-sv
  1496.                };
  1497.  
  1498. #if DEBUG_LEVEL > 1
  1499.     worth_called++;
  1500. #endif
  1501.  
  1502.     *valsum=valsum[2]=0;    /* clean out buckets    */
  1503.     ptr=t=board->array[0];    /* set up pointers        */
  1504.  
  1505.     /* and let the finite state automoton roll--one edge in each term */
  1506.     valsum[1]=
  1507.       v[f[f[f[f[f[f[f[  *t ]+t[ 1]]+t[ 2]]+t[ 3]]+t[ 4]]+t[ 5]]+t[ 6]]+t[ 7]]
  1508.      +v[f[f[f[f[f[f[f[  *t ]+t[ 8]]+t[16]]+t[24]]+t[32]]+t[40]]+t[48]]+t[56]]
  1509.      +v[f[f[f[f[f[f[f[t[ 7]]+t[15]]+t[23]]+t[31]]+t[39]]+t[47]]+t[55]]+t[63]]
  1510.      +v[f[f[f[f[f[f[f[t[56]]+t[57]]+t[58]]+t[59]]+t[60]]+t[61]]+t[62]]+t[63]];
  1511.  
  1512.     /*
  1513.         if the worth array shown in the comment above actually existed, the
  1514.         next 60 or so lines might have been written
  1515.  
  1516.             for(i=0;i<64;i++)
  1517.                 valsum[board[i]]+=worth[i];
  1518.  
  1519.         but it doesn't, except in the defined constants ev0 through ev3.
  1520.         Besides, it's quicker to execute 60 statements than to go through
  1521.         a loop 60 times (no loop control and branching) and this function
  1522.         is at the bottom of the recursion, and needs to be fast.
  1523.     */
  1524.  
  1525.     valsum[*ptr++]+=ev0;
  1526.     valsum[*ptr++]+=ev1;
  1527.     valsum[*ptr++]+=ev2;
  1528.     valsum[*ptr++]+=ev3;
  1529.     valsum[*ptr++]+=ev3;
  1530.     valsum[*ptr++]+=ev2;
  1531.     valsum[*ptr++]+=ev1;
  1532.     valsum[*ptr++]+=ev0;
  1533.  
  1534.     valsum[*ptr++]+=ev1;
  1535.     valsum[*ptr++]-=val1[*t];
  1536.     valsum[*ptr++]-=val2[t[2]];
  1537.     valsum[*ptr++]-=val3[t[3]];
  1538.     valsum[*ptr++]-=val3[t[4]];
  1539.     valsum[*ptr++]-=val2[t[5]];
  1540.     valsum[*ptr++]-=val1[t[7]];
  1541.     valsum[*ptr++]+=ev1;
  1542.  
  1543.     valsum[*ptr++]+=ev2;
  1544.     valsum[*ptr++]-=val2[t[16]];
  1545.     valsum[*ptr]++;
  1546.     ptr+=3;
  1547.     valsum[*ptr++]++;
  1548.     valsum[*ptr++]-=val2[t[23]];
  1549.     valsum[*ptr++]+=ev2;
  1550.  
  1551.     valsum[*ptr++]+=ev3;
  1552.     valsum[*ptr]-=val3[t[24]];
  1553.     ptr+=5;
  1554.     valsum[*ptr++]-=val3[t[31]];
  1555.     valsum[*ptr++]+=ev3;
  1556.  
  1557.     valsum[*ptr++]+=ev3;
  1558.     valsum[*ptr]-=val3[t[32]];
  1559.     ptr+=5;
  1560.     valsum[*ptr++]-=val3[t[39]];
  1561.     valsum[*ptr++]+=ev3;
  1562.  
  1563.     valsum[*ptr++]+=ev2;
  1564.     valsum[*ptr++]-=val2[t[40]];
  1565.     valsum[*ptr]++;
  1566.     ptr+=3;
  1567.     valsum[*ptr++]++;
  1568.     valsum[*ptr++]-=val2[t[47]];
  1569.     valsum[*ptr++]+=ev2;
  1570.  
  1571.     valsum[*ptr++]+=ev1;
  1572.     valsum[*ptr++]-=val1[t[56]];
  1573.     valsum[*ptr++]-=val2[t[58]];
  1574.     valsum[*ptr++]-=val3[t[59]];
  1575.     valsum[*ptr++]-=val3[t[60]];
  1576.     valsum[*ptr++]-=val2[t[61]];
  1577.     valsum[*ptr++]-=val1[t[63]];
  1578.     valsum[*ptr++]+=ev1;
  1579.  
  1580.     valsum[*ptr++]+=ev0;
  1581.     valsum[*ptr++]+=ev1;
  1582.     valsum[*ptr++]+=ev2;
  1583.     valsum[*ptr++]+=ev3;
  1584.     valsum[*ptr++]+=ev3;
  1585.     valsum[*ptr++]+=ev2;
  1586.     valsum[*ptr++]+=ev1;
  1587.     valsum[*ptr]+=ev0;
  1588.  
  1589.     return(valsum[1]-valsum[2]);
  1590. }
  1591.  
  1592. /*
  1593.     If worth_2 is being called, we are looking all the way to the end of
  1594.     the game, and we can use the final board as an evaluator: the worth
  1595.     of the board is the number of squares more I have than he. This number
  1596.     is shifted left 2 to attempt to make the range of values returned
  1597.     approximately comparable to worth_1, so that worth_2 can be used
  1598.     by alphabeta when we find an early game ending.
  1599. */
  1600.  
  1601. worth_2(board)
  1602. BOARD *board;
  1603. {
  1604.  
  1605.     int valsum[3]={0,0,0};
  1606.  
  1607.     char *ptr;
  1608.  
  1609. #if DEBUG_LEVEL > 1
  1610.     worth_called++;
  1611. #endif
  1612.  
  1613.     ptr=board->array[0];
  1614.     /*
  1615.         The following 64 lines could have been replaced with
  1616.             for(i=0;i<64;i++)
  1617.                 valsum[board[i]]++;
  1618.  
  1619.         but it would have been slower.
  1620.     */
  1621.     valsum[*ptr++]++;
  1622.     valsum[*ptr++]++;
  1623.     valsum[*ptr++]++;
  1624.     valsum[*ptr++]++;
  1625.     valsum[*ptr++]++;
  1626.     valsum[*ptr++]++;
  1627.     valsum[*ptr++]++;
  1628.     valsum[*ptr++]++;
  1629.     valsum[*ptr++]++;
  1630.     valsum[*ptr++]++;
  1631.     valsum[*ptr++]++;
  1632.     valsum[*ptr++]++;
  1633.     valsum[*ptr++]++;
  1634.     valsum[*ptr++]++;
  1635.     valsum[*ptr++]++;
  1636.     valsum[*ptr++]++;
  1637.     valsum[*ptr++]++;
  1638.     valsum[*ptr++]++;
  1639.     valsum[*ptr++]++;
  1640.     valsum[*ptr++]++;
  1641.     valsum[*ptr++]++;
  1642.     valsum[*ptr++]++;
  1643.     valsum[*ptr++]++;
  1644.     valsum[*ptr++]++;
  1645.     valsum[*ptr++]++;
  1646.     valsum[*ptr++]++;
  1647.     valsum[*ptr++]++;
  1648.     valsum[*ptr++]++;
  1649.     valsum[*ptr++]++;
  1650.     valsum[*ptr++]++;
  1651.     valsum[*ptr++]++;
  1652.     valsum[*ptr++]++;
  1653.     valsum[*ptr++]++;
  1654.     valsum[*ptr++]++;
  1655.     valsum[*ptr++]++;
  1656.     valsum[*ptr++]++;
  1657.     valsum[*ptr++]++;
  1658.     valsum[*ptr++]++;
  1659.     valsum[*ptr++]++;
  1660.     valsum[*ptr++]++;
  1661.     valsum[*ptr++]++;
  1662.     valsum[*ptr++]++;
  1663.     valsum[*ptr++]++;
  1664.     valsum[*ptr++]++;
  1665.     valsum[*ptr++]++;
  1666.     valsum[*ptr++]++;
  1667.     valsum[*ptr++]++;
  1668.     valsum[*ptr++]++;
  1669.     valsum[*ptr++]++;
  1670.     valsum[*ptr++]++;
  1671.     valsum[*ptr++]++;
  1672.     valsum[*ptr++]++;
  1673.     valsum[*ptr++]++;
  1674.     valsum[*ptr++]++;
  1675.     valsum[*ptr++]++;
  1676.     valsum[*ptr++]++;
  1677.     valsum[*ptr++]++;
  1678.     valsum[*ptr++]++;
  1679.     valsum[*ptr++]++;
  1680.     valsum[*ptr++]++;
  1681.     valsum[*ptr++]++;
  1682.     valsum[*ptr++]++;
  1683.     valsum[*ptr++]++;
  1684.     valsum[*ptr]++;
  1685.  
  1686.     /* return((<number I have> - <number he has>) * 2); */
  1687.     return((valsum[1]-valsum[2])<<2);
  1688. }
  1689.  
  1690. #ifdef IBMPC
  1691.  
  1692. /*
  1693.     Time_tick returns the (long) number of 100'ths of seconds since
  1694.     the day began, according to the PC's real-time clock. This is
  1695.     useful for getting elapsed time by subtracting successive times.
  1696. */
  1697.  
  1698. long time_tick()
  1699. {
  1700. #asm
  1701.     mov    ah,2ch    ; function number for get time-of-day
  1702.     int 21h        ; make DOS function call
  1703.     xor ah,ah    ; zero ah
  1704.     mov al,ch    ;
  1705.     mov bl,60    ; ax=60*ch
  1706.     mul bl        ;
  1707.     xor ch,ch    ; zero ch
  1708.     add cx,ax    ; cx=60*ch + cl is minutes
  1709.     xor ah,ah    ; zero ah
  1710.     mov al,dh    ;
  1711.     mov bl,100    ; ax=100*dh
  1712.     mul bl        ;
  1713.     xor dh,dh    ; zero dh
  1714.     add dx,ax    ; dx=100*dh + dl is hundredths of seconds
  1715.     mov bx,dx    ; stash it in bx
  1716.     xor dx,dx    ; freeing up dx
  1717.     mov ax,cx    ; ax gets minutes
  1718.     mov cx,6000 ;
  1719.     mul cx        ; times 6000 is hundredths of seconds in ax and dx
  1720.     add ax,bx    ; plus hundredths of seconds
  1721.     jae    done    ; if no carry then we are done--calling convention for
  1722.                 ; long ints in c is to return them in dx & ax
  1723.     inc dx        ; if carry, fixup dx
  1724. done:
  1725. #
  1726. }
  1727. #else
  1728.  
  1729. /* dummy routine for other systems */
  1730.  
  1731. long time_tick()
  1732. {
  1733.     return(0);
  1734. }
  1735. #endif
  1736.  
  1737.  
  1738.